package puzzle.projecteuler.p100;

import java.util.ArrayList;
import java.util.List;

import astudy.util.AdvMath;

public class Problem095C {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		long s = System.currentTimeMillis();
		int m = 1000000;
		int[] ds = d(m);
		int n = m;
		int l = 0;
		List<Integer> chain = new ArrayList<Integer>();
		for (int i = 2; i < ds.length; i ++) {
			chain.clear();
			int tmp = i;
			chain.add(tmp);
			do {
				if (tmp < m && tmp > 1) {
					tmp = ds[tmp]-tmp;
					if (chain.indexOf(tmp) < 0) {
						chain.add(tmp);
						continue;
					} else if (chain.indexOf(tmp) > 0) {
						chain.clear();
						break;
					} else {
						break;
					}
				} else {
					chain.clear();
					break;
				}
			} while (true);
//			System.out.println(i+"\t:" + chain);
			if (!chain.isEmpty()) {
				if (chain.size() > l) {
					l = chain.size();
					n = i;
				}
			}
		}
		System.out.println("n = " + n);
		System.out.println("length of chain = " + l);
		System.out.println((System.currentTimeMillis()-s) + " ms");
	}

	/**
	 * 采用类似筛法的方式，计算所有n(<m)对应的因子和d(n)
	 * @param m
	 * @return
	 */
	public static int[] d(Integer m) {
		
		int sqrt_m = (int)Math.sqrt(m)+1;
		Integer[] primes = AdvMath.primes(sqrt_m);
		
		int[] tmp = new int[m+1];
		int[] res = new int[m+1];
		for (int i = 0; i < tmp.length; i ++) {
			tmp[i] = i;
			res[i] = 1;
		}
		
		tmp[0] = -1;
		res[0] = -1;
		tmp[1] = 1;
		res[1] = 1;
		
		for (int i = 0; i < primes.length; i ++) {
			int p = primes[i];
			for (int j = p; j <= m; j += p) {
				int c = 0;
				while (tmp[j]%p == 0) {
					tmp[j] /= p;
					c ++;
				}
				res[j] *= (long)(Math.pow(p, c+1)-1)/(long)(p-1);
			}
		}
		for (int i = 1; i < tmp.length; i ++) {
			if (tmp[i] != 1) {
				res[i] *= tmp[i]+1; 
			}
		}

		return res;
	} 

}
